# -*- coding: utf-8 -*-

# __date:       2021/7/9
# __author:     Yang Chao
# __function:


class Solution:

    def isMatch1(self, s: str, p: str) -> bool:
        # 最经典的深度优先遍历算法
        def dfs(i, j):
            if j == len(p):
                return i == len(s)
            pickable = i < len(s) and p[j] in {s[i], '.'}
            if j + 1 < len(p) and p[j + 1] == '*':
                if pickable:
                    return dfs(i + 1, j) or dfs(i, j + 2)
                else:
                    return dfs(i, j + 2)
            else:
                if pickable:
                    return dfs(i + 1, j + 1)
                else:
                    return False

        return dfs(0, 0)

    def isMatch2(self, s: str, p: str) -> bool:
        # DFS 加上memo缓存
        memo = [[-1 for _ in range(len(p))] for _ in range(len(s) + 1)]

        def dfs(i, j):
            if j == len(p):
                return i == len(s)
            if memo[i][j] != -1:
                return memo[i][j]
            pickable = i < len(s) and p[j] in {s[i], '.'}
            if j + 1 < len(p) and p[j + 1] == '*':
                memo[i][j] = (pickable and dfs(i + 1, j)) or dfs(i, j + 2)
            else:
                memo[i][j] = pickable and dfs(i + 1, j + 1)
            return memo[i][j]

        return dfs(0, 0)

    def isMatch3(self, s: str, p: str) -> bool:
        # 动态规划
        dp = [[False for _ in range(len(p) + 1)] for _ in range(len(s) + 1)]
        dp[0][0] = True
        for j in range(2, len(p) + 1, 2):
            dp[0][j] = p[j - 1] == '*' and dp[0][j - 2]
        for i in range(1, len(s) + 1):
            for j in range(1, len(p) + 1):
                if p[j - 1] == '*':
                    if p[j - 2] in [s[i - 1], '.']:  # 若 s[i - 1] 可匹配
                        dp[i][j] = dp[i - 1][j] or dp[i][j - 2]  # '*'匹配多次或0次
                    else:  # 若 s[i - 1] 不可匹配
                        dp[i][j] = dp[i][j - 2]  # '*'只能匹配0次
                if p[j - 1] in [s[i - 1], '.']:  # 直接匹配
                    dp[i][j] = dp[i - 1][j - 1]
        return dp[-1][-1]